第五讲 凸集及其分离

Author
Affiliation

范翻

中央财经大学(CCFD)

标准的最优化问题

标准的最优化问题:在标量约束\(G(x) \leq c\) 下选择向量\(x\) 以最大化\(F(x)\)

  • 等值线:对于一个多变量函数\(F(x)\) 而言,使得函数值等于\(c\) 的所有可能的向量\(x\) 共同构成一条等值线,对应优化问题中的约束条件。e.g. 预算约束线,等利润线,无差异曲线

  • 上等值集:所有满足\(F(x) \geq v\) 的向量\(x\) 共同构成的集合

  • 下等值集:所有满足\(G(x) \leq c\) 的向量\(x\) 共同构成的集合

凸集的分离性质

凸集(convex set)

定义: 对于\(n\) 维空间中的点集\(S\) 而言,如果给定\(S\) 中的任意两点\(x^a = (x_1^a, \cdots, x_n^a)\)\(x^b = (x_1^b, \cdots, x_n^b)\) 以及闭区间\([0,1]\)中的任意实数\(\theta\),点\(\theta x^a + (1-\theta)x^b\) 也在点集\(S\) 中,那么称点集\(S\)凸的(convex)

  • 生产函数的下等值集是凸集,意味着什么?

  • 效用函数的上等值集是凸集,意味着什么?

凸函数

定义1(从函数出发): 如果一个函数\(G(x)\)满足,对于所有的\(x^a, x^b\)和任意\(\theta \in [0,1]\),都有 \[ G(\theta x^a + (1 - \theta)x^b) \leq \theta G(x^a) + (1 - \theta)G(x^b) \] 则称其为凸函数(convex function)

反之,若一个函数\(F(x)\)满足 \[ F(\theta x^a + (1 - \theta)x^b) \geq \theta F(x^a) + (1 - \theta)F(x^b) \] 则称其为凹函数(concave function)

凹函数

拟凸函数

从代数上看,集合\(G(x)\leq c\) 是凸集意味着: \[ G(x^a) \leq c , G(x^b) \leq c \Rightarrow G(\theta x^a + (1 - \theta) x^b) \leq c \]

如果其中一个端点的值恰好等于\(c\) 时,这个条件又可以表述为\(\forall x^a, x^b , \theta \in[0,1]\)\[ G(\theta x^a + (1 - \theta) x^b) \leq max(G(x^a), G(x^b)) \]

我们称满足上述条件的函数为拟凸函数(quasi convex function)

反之,如果函数\(F(x)\)满足 \[ F(\theta x^a + (1 - \theta) x^b) \geq min(F(x^a), F(x^b)) \] 则称其为拟凹函数(quasi concave function)

内点与边界点

  • 内点:如果存在点\(x^0\) 的邻域\(B(x^0, \delta)\) 包含于集合\(S\),则称点\(x^0\) 是集合\(S\) 的一个内点(inner point)

  • 边界点:如果一个点\(x^1\) 既不是集合\(S\)的内点,也不是集合\(S\) 的补集的内点,则称点\(x^1\) 是集合\(S\)的一个边界点(boundary points)。换言之,如果一个点\(x^1\)是集合\(S\) 的边界点,那么其任意邻域内,都既存在属于\(S\)的点,也存在不属于\(S\)的点

分散化下的局部失灵

分离定理

如果A和B为两个没有公共内点的凸集,且至少有一个集合有一个非空内点,那么我们总可以找到一个非零向量\(p\)和一个数\(b\),使得超平面\(px = b\)分离这两个集合,或:

\[ px \begin{cases} \leq b, & \forall x \in A \\ \geq b, & \forall x \in B \end{cases} \]

分离角度的最优化定理

给定拟凹函数\(F\)和拟凸函数\(G\),点\(\bar{x}\)在满足约束条件\(G(x) \leq c\)下使得\(F(x)\)最大,当且仅当存在一个非零向量\(p\),使得:

  • \(\bar{x}\)在满足\(G(x) \leq c\)下最大化\(px\)

  • \(\bar{x}\)在满足\(F(x) \geq \bar{v}\)下最小化\(px\)

经济学解释

假定\(x\)为生产-消费向量,约束反映了资源的有限性,目标函数为效用函数。\(p\)理解为产出的价格向量,那么上述定理意味着:

  • 寻求产出价格最大化的企业家会生产出最优产量\(\bar{x}\)

  • 试图以最小支出达到既定效用的消费者也恰好需要\(\bar{x}\)

  • 社会最优化问题就可以被分散化的机制实现

唯一性

严格拟凸

严格拟凸函数: \[ G(\theta x^a + (1 - \theta) x^b) < max(G(x^a), G(x^b)) \]

严格拟凹函数: \[ F(\theta x^a + (1 - \theta) x^b) > min(F(x^a), F(x^b)) \]

唯一性条件

考虑在约束\(G(x) \leq c\) 下最大化\(F(x)\)的问题,其中\(F\)为严格拟凹的,\(G\)为严格拟凸的。假定\(x\)满足分离角度的最优化定理,那么它将是该最优化问题的唯一解。【证明:反证法】